/*
提交链接:https://leetcode.cn/problems/burst-balloons/description/
312. [戳气球]
赖德檀 2024/12/04
*/

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        int n = nums.size() - 2;
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        for (int len = 3; len <= n + 2; len++) { 
            for (int l = 0; l <= n + 2 - len; l++) { 
                int r = l + len - 1; 
                for (int t = l + 1; t < r; t++) {
                    dp[l][r] = max(
                        dp[l][r],
                        nums[l] * nums[t] * nums[r] + dp[l][t] + dp[t][r]
                    );
                }
            }
        }  
        return dp[0][n + 1];
    }
};